import java.util.ArrayList;
import java.util.List;

public class FindAnagrams {
    // leetcode hot 100 找到字符串中所有字母异位词
    // https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for (char c : pp) hash1[c - 'a']++;
        for (int left = 0, right = 0, count = 0; right < ss.length; right++) {
            char in = ss[right];
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            // 窗口中只维护p字符串长度的字符串，如果窗口大小过大的话，就需要出窗口
            if (right-left + 1 > pp.length) {
                char out = ss[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            // 如果窗口大小符合的话，判断窗口中的字母是否都符合
            if (count == pp.length) {
                ret.add(left);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        FindAnagrams findAnagrams = new FindAnagrams();
        findAnagrams.findAnagrams("cbaebabacd","abc");
        System.out.println(555);
    }
}
